package com.leetcode.algorithm.y22.m05;

/**
 * 152. 乘积最大子数组
 * https://leetcode.cn/problems/maximum-product-subarray/description/
 * 
 * @author jie.deng
 *
 */
class Question0152Solution01 {

	public int maxProduct(int[] nums) {
		int len = nums.length;
		// DP状态定义：
		// dp[i][0]表示 nums[j...i]{j>=0&&j<=i}的最大乘积
		// dp[i][1]表示 nums[j...i]{j>=0&&j<=i}的最小乘积
		int[][] dp = new int[len][2];
		// 初始化状态
		dp[0][0] = nums[0];
		dp[0][1] = nums[0];

		// 状态转移方程
		for (int i = 1; i < len; i++) {
			if (nums[i] >= 0) {
				dp[i][0] = Math.max(dp[i - 1][0] * nums[i], nums[i]);
				dp[i][1] = Math.min(dp[i - 1][1] * nums[i], nums[i]);
			} else {
				dp[i][0] = Math.max(dp[i - 1][1] * nums[i], nums[i]);
				dp[i][1] = Math.min(dp[i - 1][0] * nums[i], nums[i]);
			}
		}

		// 乘积最大:max(dp[0...len-1][0])
		int maxProduct = dp[0][0];
		for (int i = 1; i < len; i++) {
			maxProduct = Math.max(maxProduct, dp[i][0]);
		}
		return maxProduct;
	}

}